package com.michael.demos.base.java.sort;

import java.util.Arrays;

/**
 * 类功能描述:
 * <pre>
 *   堆排序
 *   1. 创建一个堆 H[0……n-1]；
 *   2. 把堆首（最大值）和堆尾互换；
 *   3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
 *   4. 重复步骤 2，直到堆的尺寸为 1；
 * </pre>
 *
 * @author Michael
 * @version 1.0
 * @date 2020/9/24 9:34
 */
public class HeapSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int len = arr.length;

        // 生成大项堆
        buildMaxHeap(arr, len);

        for (int i = len - 1; i > 0; i--) {
            // 交换数据 - 大值排最后
            swap(arr, 0, i);
            // 调整大项堆结构
            heapify(arr, 0, i);
        }
        return arr;
    }

    private void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
